#pragma once
template<typename T>
class heap
{
public:
	explicit heap(size_t cap): elems_(NULL), capacity_(cap), size_(t)
	{
		elems_ = new T[cap];
	}

	~heap()
	{
		if( elems != NULL )
		{
			delete[] elems;
			elems = NULL;
		}
	}

	bool insert( const T& elem)
	{
		if( size_ + 1 < capacity_ )
			return false;
		//Implement 
		int cur = size_++;
		elems_[cur] = elem;
		while( cur != 0 && elem_[cur] > elem_[parent(cur)])
		{
			swap(elems_, cur, parent(cur));
			cur = parent(cur);
		}
		//
		return true;
	}

	bool removeMax()
	{
		if( size_ == 0 ) return false;
		swap(heap, 0, --n); //move the max to the end;
		if( n != 0 ) siftdown(0);
		return true;
	}

	void buildUp( T* a )
	{
		if( elems_ !=  NULL )
		{
			delete[] elems_;
			elems_ = NULL;
		}
		for( size_t i = n/2 -1; i >=0; i--)
		{
			siftdown(i);
		}
	}

	static void swap( T* a, size_t l, size_t r)
	{
		try{
			T temp = a[l];
			a[l]= a[r];
			a[r]= temp;
		}
		catch(...)
		{
			//Alert
			return;
		}
	}
private:
	bool isLeaf(size_t pos) const
	{
		return pos > size_/2 && pos < size_;
	}

	size_t leftChild( size_t pos ) const
	{
		return 2*pos + 1;
	}

	size_t rightChild( size_t pos ) const
	{
		return 2*pos + 2;
	}
	size_t parent( size_t pos ) const 
	{
		return (pos-1)/2;
	}
	void siftdown( size_t pos ) 
	{
		//If pos is leaf, end()
		while( !isLeaf(pos))
		{
			size_t n = leftChild(pos);
			size_t right = rightChild(pos);
			if( elems_[right] > elems_[n])
				n = right;
			if( elems_[pos] >= elems_[n] )
				return;
			swap(elems_, pos, n);
			pos = n;
		
		}
	}



private:
	T*  elems_;
	size_t  capacity_;
	size_t  size_;
};